#include "MergeSort.h"

double MergeSort::ordenar()
{
    if (vetor == NULL) return(-1);
    tempo_iniciar();

    // Alocar vetor auxiliar:
    auxiliar = new (nothrow) byte[tamanho_vetor*tamanho_elemento];
    if (auxiliar == NULL) return(-1);

    // Executar recursivamente o MergeSort:
    mergesort(0,tamanho_vetor-1);

    // Desalocar o vetor auxiliar:
    delete[] (byte*)auxiliar;
    auxiliar = NULL;

    return(tempo_terminar());
}

void MergeSort::mergesort(size_t inicio, size_t fim)
{
    if (inicio == fim) return;

    size_t meio = (inicio + fim)/2;

    mergesort(inicio,meio);
    mergesort(meio+1,fim);

    size_t esq = inicio;
    size_t dir = meio + 1;
    size_t e = esq;
    size_t d = dir;

    // Combinar os vetores esquerdo e direito:
    // * Limites do vetor esquerdo: esq <= e <= meio
    // * Limites do vetor direito : dir <= d <= fim
    for (size_t i=inicio ; i<=fim ; i++)
    {
        // Se os dois vetores NÃO estiverem vazios:
        if ((e <= meio) && (d <= fim))
        {
            // Selecionar o menor elemento dentre as cabeças dos dois vetores:
            if (funcao_comparacao(get(e),get(d)) <= 0)
            {
                // auxiliar[i] = vetor[e]:
                atribuir(auxiliar,i,vetor,e);
                e++;
            }
            else
            {
                // auxiliar[i] = vetor[d]:
                atribuir(auxiliar,i,vetor,d);
                d++;
            }
            continue;
        }

        // Se SOMENTE o vetor esquerdo estiver vazio:
        if ((e > meio) && (d <= fim))
        {
            // auxiliar[i] = vetor[d]:
            atribuir(auxiliar,i,vetor,d);
            d++;
            continue;
        }

        // Se SOMENTE o vetor direito estiver vazio:
        if ((e <= meio) && (d > fim))
        {
            // auxiliar[i] = vetor[e]:
            atribuir(auxiliar,i,vetor,e);
            e++;
            continue;
        }
    }

    for (size_t i=inicio ; i<=fim ; i++) atribuir(vetor,i,auxiliar,i);//vetor[i] = auxiliar[i];
}

void MergeSort::atribuir(void* destino, size_t d, void* origem, size_t o)
{
    if(d >= tamanho_vetor) return;
    if(o >= tamanho_vetor) return;
    if ((destino == NULL) || (origem == NULL)) return;

    byte* de   = (byte*)origem+tamanho_elemento*o;
    byte* para = (byte*)destino+tamanho_elemento*d;

    // destino[d] = origem[o]:
    memcpy(para,de,tamanho_elemento);
}
